package leetCode.solution;

import java.util.HashMap;

/**
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * 
 * 问总共有多少条不同的路径？
 * 
 * @author jerry
 * @ClassName: Solution62
 * @Description:
 * @date 2022年11月11日 上午10:26:23
 */
public class Solution62 {
	public static void main(String[] args) {
		
		long start1 = System.currentTimeMillis();
		System.out.println(new Solution62().uniquePaths(19, 13) + " " + (System.currentTimeMillis()-start1));
		long start2 = System.currentTimeMillis();
		System.out.println(new Solution62().dp(19, 13) + " " + (System.currentTimeMillis()-start2));
	}

	public int uniquePaths(int m, int n) {
		// 经测试 数组比hashmap节省内存
//		HashMap map = new HashMap<>();
		int[][] arr = new int[m+1][n+1];

		return recursion(m, n, 0, 0, arr);
	}

	// 纯暴力递归不能AC
	// 暴力递归-> 记忆化搜索
	private int recursion(int m, int n, int x, int y, int[][] arr) {
		if(arr[x][y]>0) {
			return arr[x][y];
		}
		
		int result = 0;
		if (x == m - 1 && y == n - 1) {
			arr[x][y] = 1;
			return 1;
		}
		if (x < m && y < n) {
			result = recursion(m, n, x + 1, y, arr) + recursion(m, n, x, y + 1, arr);
			arr[x][y] = result;
		}
		return result;
	}

	// 暴力递归 --> 动态规划
	private int dp(int m, int n) {
		int[][] dp = new int[m+1][n+1];
		for(int j =0;j<=n-1;j++) {
			dp[m-1][j]=1;
		}
		for(int i =0;i<=m-1;i++) {
			dp[i][n-1]=1;
		}
		for(int i=m-2;i>=0;i--) {
			for(int j=n-2;j>=0;j--) {
				dp[i][j]=dp[i][j+1]+dp[i+1][j];
			}
		}
		return dp[0][0];
	}
}
